import sys
sys.path.append("/Users/ender/Code_repo/rosalind-brush-questions")
from utils import read_fasta
import numpy as np

"""
尽管使用了字典来记录重复计算的值，但是递归有最大深度限制，因此使用矩阵数组的迭代实现前面的递归过程：
- 构建 (m+1) * (n+1) 空矩阵数组, L；
- 遍历 i -> (m+1) 和 j -> (n+1)，根据如下规则填充矩阵数据：
    - i = 0 或 j = 0 填充为 0； # 即首行和首列填充为零
    - s1[i - 1] == s2[j - 1]: L[i][j] = L[i - 1][j - 1] + 1;
    - s1[i - 1] != s2[j - 1]: L[i][j] = max(L[i - 1][j], L[i][j - 1])
    - 最终 L[m, n] 就是 LCS
- 回溯取得其中一条 LCS 序列, lsc=''：
    - 从右下角至左上角回溯, i = m, j = n；
    - s1[i] == s2[j]: lsc += s1[i], i -= 1, j -= 1;
    - L[i - 1][j] > L[i][j - 1]: i -= 1;  # 因为当前 s1[i] != s2[j] 故没有共同字符需要添加到 lsc
    - L[i - 1][j] <= L[i][j - 1]: j -= 1; # 同理，没有共同字符需要添加到 lsc
    - 迭代结束，lsc 取反输出
"""

def build_matrix(s1: str, s2: str, m: int, n: int) -> np.ndarray:
    matrix = np.zeros((m + 1, n + 1), dtype=int)

    # 上面的矩阵是零矩阵，所以不需要再进行首行和首列的零填充了
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                matrix[i][j] = matrix[i - 1][j - 1] + 1
            else:
                matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])
    return matrix


def backtrace(s1: str, s2: str, m: int, n: int, l: np.ndarray) -> str:
    i, j = m, n
    lcs = ''    
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs += s1[i - 1]
            i -= 1
            j -= 1
        elif l[i - 1][j] > l[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return lcs[::-1]


# fasta = read_fasta("./15_FindingSharedSplicedMotif/test.txt")
# fasta = read_fasta("./test.txt")
# fasta = read_fasta("./15_FindingSharedSplicedMotif/rosalind_lcsq.txt")
fasta = read_fasta("./rosalind_lcsq (2).txt")
s1, s2 = [v for v in fasta.values()]
l = build_matrix(s2, s1, len(s2), len(s1))
lcs_length = l[len(s2)][len(s1)]
lcs = backtrace(s2, s1, len(s2), len(s1), l)
# print(l)
print(lcs_length)
print(lcs)

# print(find_longest_common_subsequence(s2, s1, matrix, 0, 0))
